package com.squirrel.michale.sort3;

import java.util.Arrays;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/3 9:07 AM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode2545 {

    public int[][] sortTheStudents(int[][] score, int k) {
        Arrays.sort(score, (a, b) -> b[k] - a[k]);
        return score;
    }


    // 二维数组的堆排序
    public int[][] sortTheStudents2(int[][] score, int k) {




        Arrays.sort(score, (a, b) -> b[k] - a[k]);
        return score;
    }

    public void sortScore(int[] score) {

        if (score == null || score.length < 2) {
            return;
        }
        for (int i = score.length - 1; i >= 0; i--) {
            heapify(score, i, score.length);
        }
        int heapSize = score.length;
        swap(score, 0, --heapSize);
        // O(N*logN)
        while (heapSize > 0) { // O(N)
            heapify(score, 0, heapSize); // O(logN)
            swap(score, 0, --heapSize); // O(1)
        }
    }


    public static void heapInsert(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    // arr[index]位置的数，能否往下移动
    public static void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1; // 左孩子的下标
        while (left < heapSize) { // 下方还有孩子的时候
            // 两个孩子中，谁的值大，把下标给largest
            // 1）只有左孩子，left -> largest
            // 2) 同时有左孩子和右孩子，右孩子的值<= 左孩子的值，left -> largest
            // 3) 同时有左孩子和右孩子并且右孩子的值> 左孩子的值， right -> largest
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            // 父和较大的孩子之间，谁的值大，把下标给largest
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }


    public static void main(String[] args) {
        int[] score = new int[]{9,11,3};

        LeetCode2545 leetCode2545 = new LeetCode2545();
        leetCode2545.sortScore(score);
        System.out.println(Arrays.toString(score));
    }

}
